默写2.java
/**
1、思路
2、关键点
3、对比，考察什么，有哪些启发
 */



class Solution {
    /**
    给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 
    */
    public boolean hasPathSum(TreeNode root, int sum) {
        //边界非常重要
        if (root == null) {
            return false;
        }
        //叶子节点终止条件。
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        //递归核心,查找 (左或者右就可以了)。 sum - root.val
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
    /**
     比较两颗二叉树是否是相同的
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //边界非常重要 1 都未null  2 一个为null 
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        //终止条件，遍历到null， 所有的节点value必须相等    
        } else if (p.val != q.val) {
            return false;
        } else {
        //并且    
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

/**
    验证是否合法二叉排序树
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper) {
        
        //所有的都不为false，直到null。
        if (node == null) {
            return true;
        }
        //2.验证都是判断false node.val必须是中间值。
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        //并且关系、 左树小于root  ，右树大于root
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }

   
    //中序遍历
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
            stack.push(root);
            root = root.left;
            }
            root = stack.pop();

            if(pre != null && root.val <= pre.val) return false;
      
            pre = root;
            root = root.right;
        }
    return true;
    }
}

/**
层序遍历。
 */
public void cengxu(Node t) {//层序遍历
    //记住ArrayDeque
	Queue<node> q1 = new ArrayDeque<node>();
	if (t == null)
		return;
    //初始化，root入队    
	if (t != null) {
		q1.add(t);
	}
    //当前节点的下一层放在队尾，循环执行。
	while (!q1.isEmpty()) {
        //直到第n层的最后一个poll出来，第n+1层的还在队列中整齐排着。这就达到一个层序的效果
		node t1 = q1.poll();

		if (t1.left != null)
			q1.add(t1.left);
		if (t1.right != null)
			q1.add(t1.right);

		System.out.print(t1.value + " ");
	}
}


/*** 

判断是不是二叉搜索树的后续遍历

思路：
1.最后一个值是root

2. while (postorder[mid] < root) mid++ . 找到  第一个比根节点大的值mid 赋值temp

while(temp < right)
3.判断  mid后面的值是否小于root， false

//左半边，右半边， left mid right 右区间都要减1
4.递归 helper(postorder, left, mid - 1) && helper(postorder, mid, right - 1);
*/

public boolean verifyPostorder(int[] postorder) {
    //postorder.length - 1 注意是减1
    return helper(postorder, 0, postorder.length - 1);
}

boolean helper(int[] postorder, int left, int right) {
    //边界条件。只有1个节点或者没有节点
    if (left >= right){
        return true;
    }    

    //数组中最后一个值postorder[right]是根节点...
    int root = postorder[right];
    //这里从左往右找出第一个比根节点大的值
    int mid = left;
    while (postorder[mid] < root){
        mid++;
    }
    
    //因为postorder[mid]前面的值都是比根节点root小的，
    //我们还需要确定postorder[mid]后面的值都要比根节点root大，
    //如果后面有比根节点小的直接返回false
    int temp = mid;
    while (temp < right) {
        if (postorder[temp++] < root)
            return false;
    }
    //然后对左右子节点进行递归调用
    return helper(postorder, left, mid - 1) && helper(postorder, mid, right - 1);
}

/**
2.栈的方式

遍历数组的所有元素，如果栈为空，就把当前元素压栈。
如果栈不为空，
并且当前元素大于栈顶元素，说明是升序的，那么就说明当前元素是栈顶元素的右子节点，就把当前元素压栈，如果一直升序，就一直压栈。
当前元素小于栈顶元素，说明是倒序的，说明当前元素是某个节点的左子节点，我们目的是要找到这个左子节点的父节点，就让栈顶元素出栈，直到栈为空或者栈顶元素小于当前值为止，其中最后一个出栈的就是当前元素的父节点
 */

 public boolean verifyPostorder(int[] postorder) {
    Stack<Integer> stack = new Stack<>();
    int parent = Integer.MAX_VALUE;
    //注意for循环是倒叙遍历的
    for (int i = postorder.length - 1; i >= 0; i--) {
        int cur = postorder[i];
        //当如果前节点小于栈顶元素，说明栈顶元素和当前值构成了倒叙，
        //说明当前节点是前面某个节点的左子节点，我们要找到他的父节点
        while (!stack.isEmpty() && stack.peek() > cur)
            parent = stack.pop();
        //只要遇到了某一个左子节点，才会执行上面的代码，才会更
        //新parent的值，否则parent就是一个非常大的值，也就
        //是说如果一直没有遇到左子节点，那么右子节点可以非常大
        if (cur > parent)
            return false;
        //入栈
        stack.add(cur);
    }
    return true;
}

//反转二叉树
/**
反转当前值
左右再反转
 */
 class Solution {
	public TreeNode invertTree(TreeNode root) {
		//递归函数的终止条件，节点为空时返回
		if(root==null) {
			return null;
		}
		//下面三句是将当前节点的左右子树交换
		TreeNode tmp = root.right;
		root.right = root.left;
		root.left = tmp;
		//递归交换当前节点的 左子树
		invertTree(root.left);
		//递归交换当前节点的 右子树
		invertTree(root.right);
		//函数返回时就表示当前这个节点，以及它的左右子树
		//都已经交换完了
		return root;
	}
}

//借用于栈的中序遍历
/**
它的规则大致为：

1、栈依次存入左节点所有点，直到最左侧在栈顶。
2、开始抛出栈顶并访问。
    如果有右节点。那么将右节点加入栈中，然后右节点一直左下遍历直到尾部。就这样循环下去直到栈为空。

可行性分析：中序是左—中—右的顺序。
访问完左侧。当抛出当前点的时候说明左侧已经访问完(或者自己就是左侧)，那么需要首先访问当前点的右侧。那么这个右节点把它当成根节点重复相同操作（因为右节点要满足先左再右的顺序）。
这样其实就是模拟了一个递归的过程，需要自己思考
 */
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;

    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()){
        //left全部入栈
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;
    }
    return list;
}


/**
中序遍历，遭到二叉树中第K小的数
 */
public int kthSmallest(TreeNode root, int k) {
     Stack<TreeNode> stack = new Stack<>();
     while(root != null || !stack.isEmpty()) {
         while(root != null) {
             stack.push(root);    
             root = root.left;   
         } 
         root = stack.pop();
         //注意是--k
         if(--k == 0) break;
         root = root.right;
     }
     return root.val;
 }

 /**
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。
 */

class Solution {
    public int maxDepth(TreeNode root){
        //首先记住边界，而且边界一般也是终止条件
        if(root == null){
            return  0;
        }else{
            return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1 ;
        }
    }
}

/** 
递归遍历

traverse(root.left);
...
traverse(root.right);

*/


/**
思路： 同时遍历两个链表，下个节点指向哪个链表的头，直到null，然后再挂接上剩下的链表。
 */
public ListNode mergeTwoLists(ListNode l1,ListNode l2){
  
    ListNode head =new ListNode(0);
    ListNode handler = head;


    while(l1!=null && l2!=null){
        if(l1.value <= l2.value){
            handler.next = l1;
            l1 =  l1.next;
        }else{
            handler.next = l2;
            l2 = l2.next;
        }
    }

    if(l1!=null){
        handler.next = l1;
    }else{
        handler.next = l2;
    }
    //返回head
    return head.next;
}


/**
思路:  
current最后current.next,但“next要调转为pre”,所以next"首先"暂存为temp。
最后return pre。借助于pre和current两个变量。
 */
ListNode reverseList(ListNode head ){

    ListNode pre = null;
    ListNode current = head;

    while( current != null && current.next != null ){
        //current的下一个节点暂存
        ListNode  next = current.next;
        current.next = pre;
        
        pre = current;
        //以更新current截止
        current = next;
    }
    return pre;
}


//反转部分链表
//https://leetcode.com/problems/reverse-linked-list-ii/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) return null;
        ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
        dummy.next = head;

        ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing
        //m-1 pre节点
        for(int i = 0; i<m-1; i++) pre = pre.next;
    
        // a pointer to the beginning of a sub-list that will be reversed
        ListNode start = pre.next; 

        // a pointer to a node that will be reversed
        ListNode then = start.next; 
    
        // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
        // dummy-> 1 -> 2 -> 3 -> 4 -> 5
    
        for(int i = 0; i< n-m; i++){
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }
    
        // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
        // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
        return dummy.next;
}


public class Solution {



    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 因为头结点有可能发生变化，使用虚拟头结点可以避免复杂的分类讨论
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // 第 1 步：从虚拟头结点走 left - 1 步，来到 left 结点的前一个结点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 结点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        // 注意：切断链接
        pre.next = null;
        rightNode.next = null;

        // 第 4 步：同第 206 题，反转链表的子区间
        reverseLinkedList(leftNode);

        // 第 5 步：接回到原来的链表中
        pre.next = rightNode;
        leftNode.next = curr;
        return dummyNode.next;
    }

    //技巧思路 暂不记忆 https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
}

/***
  合并K个排序链表，使用优先级队列 
 */
  public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists==null||lists.size()==0) return null;
        
        PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
            @Override
            public int compare(ListNode o1,ListNode o2){
                if (o1.val<o2.val)
                    return -1;
                else if (o1.val==o2.val)
                    return 0;
                else 
                    return 1;
            }
        });
        
        ListNode dummy = new ListNode(0);
        ListNode tail=dummy;
        
        for (ListNode node:lists){
            if (node!=null){
                queue.add(node);
            }
        }

        while (!queue.isEmpty()){
            tail.next = queue.poll();
            tail = tail.next;
            
            if (tail.next != null){
                queue.add(tail.next);
            }
        }
        return dummy.next;
    }
}

/***
  归并排序
   */
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;
        
    // step 1. cut the list to two halves
    ListNode prev = null, slow = head, fast = head;
    
    while (fast != null && fast.next != null) {
      prev = slow;
      slow = slow.next;
      fast = fast.next.next;
    }
    
    // 切断链表
    prev.next = null;
    
    // step 2. sort each half
    ListNode l1 = sortList(head);
    ListNode l2 = sortList(slow);
    
    // step 3. merge l1 and l2
    return mergeTwoLists(l1, l2);
  }


  /**
https://leetcode.com/problems/swap-nodes-in-pairs

Given a linked list, swap every two adjacent nodes and return its head.
**/   
   
public ListNode swapPairs(ListNode head) {
    if ((head == null)||(head.next == null))
        return head;
    ListNode n = head.next;
    head.next = swapPairs(head.next.next);
    n.next = head;
    return n;
}

/**
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
1.最简单情况 双指针同时检查  如果s.charAt(left)!=s.charAt(right)，就为false。直到最后未false就为true了。
2.但是左右都要忽略 !Character.isLetterOrDigit 的情况
3.忽略大小写，所以toLowerCase来判断是否!=
 */

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int left = 0, right = n - 1;
        
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                ++left;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                --right;
            }
            //还是要再判断一次
            if (left < right) {
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
}

/***
反转字符串与反转数组类似 char[] word = s.toCharArray()。
left<right  right = len -1
 */
public String reverseString(String s) {
        char[] word = s.toCharArray();
        int i = 0;
        int j = s.length() - 1;
        while (i < j) {
            char temp = word[i];
            word[i] = word[j];
            word[j] = temp;
            
            i++;
            j--;
        }
        return new String(word);
}

/*** 
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

思路：
1.遍历一次，记录所有的频率， 然后再把相同频率的放在一次。
2.数据结构，map存储每个key的频率。频率次数使用数组，数组下标为频率数。所以从高到低，只需要倒序输出就可以了。
3.频率最高为数组长度，申请频率数组长度+1
*/

public List<Integer> topKFrequent(int[] nums, int k) {
    //频率
	List<Integer>[] bucket = new List[nums.length + 1];

	//每个元素出现的频率
	Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
	for (int n : nums) {
		frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
	}

	//每个频率，对应的元素列表
	for (int key : frequencyMap.keySet()) {
		int frequency = frequencyMap.get(key);
		if (bucket[frequency] == null) {
			bucket[frequency] = new ArrayList<>();
		}
		bucket[frequency].add(key);
	}

	List<Integer> res = new ArrayList<>();
	//从频率高到低取出结果
	for (int pos = bucket.length - 1; pos >= 0 && res.size() < k;  pos--) {
		if (bucket[pos] != null) {
			res.addAll(bucket[pos]);
		}
	}
	return res;
}

/**
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
删除为0 
思路：把所有不为0的值交换到当前指针位置
*/


    public void moveZeroes(int[] nums) {
        int indexNow = 0;
        int indexNum = 0;
        int m = nums.length;

        while(indexNum<m){
            if(nums[indexNum] != 0) {
                nums[indexNow++] = nums[indexNum];
            }
            ++indexNum;
        }

        for(int i = indexNow; i < m; i++){
            nums[i] = 0;
        }
    }

/***

基本操作.java

给定一个目录信息列表，包括目录路径，以及该目录中的所有包含内容的文件，您需要找到文件系统中的所有重复文件组的路径。一组重复的文件至少包括二个具有完全相同内容的文件。


输入：
["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]
输出：  
[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]
 */

public class Solution {
    public List < List < String >> findDuplicate(String[] paths) {
        HashMap < String, List < String >> map = new HashMap < > ();
        for (String path: paths) {
            String[] values = path.split(" ");
            for (int i = 1; i < values.length; i++) {
                String[] name_cont = values[i].split("\\(");
                name_cont[1] = name_cont[1].replace(")", "");
                List < String > list = map.getOrDefault(name_cont[1], new ArrayList < String > ());
                list.add(values[0] + "/" + name_cont[0]);
                map.put(name_cont[1], list);
            }
        }
        List < List < String >> res = new ArrayList < > ();
        for (String key: map.keySet()) {
            if (map.get(key).size() > 1)
                res.add(map.get(key));
        }
        return res;
    }
}

/**
链表中倒数第K个节点
**/
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow=head,fast=head;
        int t = 0;
        while(fast != null){
            if(t >= k){
                slow = slow.next;
            } 
            fast = fast.next;
            t++;
        }
        return slow;
    }
}

/**
https://leetcode.com/problems/first-unique-character-in-a-string
Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.
 */

public int firstUniqChar(String s) {
    if (s == null || s.isEmpty()) return -1;
    
    int[] freq = new int[26];
    //记录每个字符的次数
    for(int i = 0; i < s.length(); i ++){
        freq [s.charAt(i) - 'a'] ++;
    }    
    for(int i = 0; i < s.length(); i ++){
        if(freq [s.charAt(i) - 'a'] == 1){
            return i;
        }
    }
    return -1;
}

/**
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
https://leetcode-cn.com/problems/first-missing-positive/solution/javade-6chong-jie-fa-de-tu-wen-xiang-jie-wei-yun-s/
 */

    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            //如果在指定的位置就不需要修改
            if (i + 1 == nums[i])
                continue;
            int x = nums[i];
            
            //是正整数才处理
            if (x > 0 && x <= nums.length && x != nums[x - 1]) {
                swap(nums, i, x - 1);
                i--;//抵消上面的i++，如果交换之后就不++；
            }
        }
        //最后在执行一遍循环，查看对应位置的元素是否正确，如果不正确直接返回
        for (int i = 0; i < nums.length; i++) {
            if (i + 1 != nums[i])
                return i + 1;
        }
        return nums.length + 1;
    }

    //交换两个数的值
    public void swap(int[] A, int i, int j) {
        if (i != j) {
            A[i] ^= A[j];
            A[j] ^= A[i];
            A[i] ^= A[j];
        }
    }

/**
https://leetcode.com/problems/sort-array-by-parity/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
**/

public int[] sortArrayByParity(int[] A) {
    int size = A.length;
    int start = 0, end = size - 1;
    int[] res = new int[size];
    for (int i = 0; i < size; i++) {
        if (A[i] % 2 == 1) {
            res[end--] = A[i];
        } else {
            res[start++] = A[i];
        }
    }
    return res;
}    


/**
 * 
https://leetcode.com/problems/sort-array-by-parity-ii
//遍历一遍数组把所有的偶数放进 ans[0]，ans[2]，ans[4]，依次类推。
再遍历一遍数组把所有的奇数依次放进 ans[1]，ans[3]，ans[5]，依次类推。
----------------
//为数组的偶数下标部分和奇数下标部分分别维护指针 i, ji,j。随后，在每一步中，如果 A[i]A[i] 为奇数，则不断地向前移动 jj（每次移动两个单位），直到遇见下一个偶数。此时，可以直接将 A[i]A[i] 与 A[j]A[j] 交换。我们不断进行这样的过程，最终能够将所有的整数放在正确的位置上。
 */

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int n = A.length;
        int j = 1;
        for (int i = 0; i < n; i += 2) {
            if (A[i] % 2 == 1) {
                while (A[j] % 2 == 1) {
                    j += 2;
                }
                swap(A, i, j);
            }
        }   
        return A;
    }

    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}



/**
https://leetcode.com/problems/squares-of-a-sorted-array/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china


Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

因为原数组是有序的，但是包含负数,如果负数存在，按照原来顺序平方之后的数组，两头大，中间小
直观的想法是先找到平方最小的数，即“最接近 0” 的数，再向两侧展开 merge两个有序数组。
但是这样就还需要先找 0 ，不如从两侧向中心逼近，最后再将数组逆序

所以，根据绝对值大小来判断，使用双指针从两端向中心靠拢，得到平方数组之后逆序

**/

class Solution {
    public int[] sortedSquares(int[] A) {
        int n = A.length;
        int[] result = new int[n];
        int i = 0, j = n - 1;

        //先申请相同长度的数组，再从后面往前依次填入
        for (int p = n - 1; p >= 0; p--) {
            if (Math.abs(A[i]) > Math.abs(A[j])) {
                result[p] = A[i] * A[i];
                i++;
            } else {
                result[p] = A[j] * A[j];
                j--;
            }
        }
        return result;
    }
}

/**
  数组的交集，实际上就是集合求交
*/
public int[] intersect(int[] nums1, int[] nums2) {
    // freq count for nums1
    HashMap<Integer, Integer> map = new HashMap();
    for (int num : nums1) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
        
        // collect result
    ArrayList<Integer> result = new ArrayList();
    for (int num: nums2) {
        if (map.containsKey(num)){
            result.add(num);
            map.put(num, map.get(num) - 1);
            map.remove(num, 0);
        }
    }
       // convert result
    int[] r = new int[result.size()];
    for(int i = 0; i < result.size(); i++) {
        r[i] = result.get(i);
    }
    return r;
}




/**
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。
 * m1:
 * 1. a+b=target, a=target-b
 * 2. 使用map找到目标值
 */
public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(target - numbers[i])) {
            result[1] = i;
            result[0] = map.get(target - numbers[i]);
            return result;
        }

        map.put(numbers[i], i);
    }
    return result;
}

    //排序后双指针，因为可以二分
    public List<List<Integer>> threeSum(int[] nums) {// 总时间复杂度：O(n^2)
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) return ans;

        //可以排序或交换
        Arrays.sort(nums); // O(nlogn)

        for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
            if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了

            if (i > 0 && nums[i] == nums[i - 1]) continue; //  去掉重复情况.当前的值等于前面的值

            int target = 0-nums[i];
            
            int left = i + 1, right = nums.length - 1;

            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                    
                    // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                    left++; right--; // 首先无论如何先要进行加减操作

                    //排重
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;

                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else (nums[left] + nums[right] > target) {  
                    right--;
                }
            }
        }
        return ans;
}

/**
 * https://leetcode-cn.com/problems/decode-string

 给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

输入：s = "3[a]2[bc]"
输出："aaabcbc"
*/
//数字一个栈，字母一个栈
public String decodeString(String s) {
		StringBuffer ans = new StringBuffer();
		Stack<Integer> multiStack=new Stack<>();
		Stack<StringBuffer> ansStack=new Stack<>();
		int multi=0;
		for(char c:s.toCharArray()){
			if(Character.isDigit(c)) multi = multi*10 + c-'0';
			else if(c=='['){
				ansStack.add(ans);
				multiStack.add(multi);
				ans=new StringBuffer();
				multi=0;
			}else if(Character.isAlphabetic(c)){
				ans.append(c);
			}else{
				StringBuffer ansTmp = ansStack.pop();
				int tmp = multiStack.pop();
				for(int i=0;i<tmp;i++){
                    ansTmp.append(ans);
                }    
				ans = ansTmp;
			}
		}
		return ans.toString();
} 

//有效的括号
//
public boolean isValid(String s) {
	Stack<Character> stack = new Stack<Character>();
	for (char c : s.toCharArray()) {
		if (c == '(')
			stack.push(')');
		else if (c == '{')
			stack.push('}');
		else if (c == '[')
			stack.push(']');
		else if (stack.isEmpty() || stack.pop() != c)
			return false;
	}
	return stack.isEmpty();
}


/** 
https://leetcode-cn.com/problems/longest-valid-parentheses
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
*/

/**
遍历给定字符串的过程中去判断到目前为止扫描的子串的有效性，同时能得到最长有效括号的长度
1.左入栈，
2.右弹出
    站为空，入栈
    否则，更新结果 i-stack.peek()
 */
public class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        //始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」
        //边界比较关键
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            //对于遇到的每个 ‘(’ ，我们将它的下标放入栈中
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();

                if (stack.empty()) {
                    //如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
                    stack.push(i);
                } else {
                    //如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}

/**

这种逆波兰式本质上是表达式的后缀表示。人不太好理解。但是计算机计算起来非常方便。是经典的栈处理。
    维护一个运算数栈，遇到运算数就压栈，
    遇到运算符就出栈两个栈顶的元素进行运算（加减乘除），
    
    然后将结果重新放回栈顶。
    
    唯一需要注意的是因为减法和除法不满足交换律，所以要用栈顶的前一个元素作为左操作数，栈顶元素作为右操作数计算。否则计算错误。

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < tokens.length; i++) {
            switch (tokens[i]) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int a = stack.pop();
                    stack.push(stack.pop() - a); //第二个栈顶减第一个栈顶
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int b = stack.pop();
                    stack.push(stack.pop() / b); //第二个栈顶除以第一个栈顶
                    break;
                default:
                    stack.push(Integer.parseInt(tokens[i]));
                    break;
            }
        }
        return stack.pop();
    }
}

/** 
https://leetcode.com/problems/find-the-difference
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
 */

//---等价于只出现一次的字符。  从头到尾^, 起始值可以是0
class Solution {
     public char findTheDifference(String s, String t) {
        char res = 0;
        for (char c: s.toCharArray()) {
            res ^= c;
        }
        for (char c: t.toCharArray()) {
            res ^= c;
        }
        return res;
    }
}

/***
寻找缺失的元素
所有的索引和value ^ , res ^= i ^ nums[i];  不要忘记了res^n 因为少了一个数
 */
int missingNumber(int[] nums) {
    int n = nums.length;
    int res = 0;
    // 先和新补的索引异或一下 --因为缺失了一个数字
    res ^= n;
    // 和其他的元素、索引做异或
    for (int i = 0; i < n; i++)
        res ^= i ^ nums[i];
    return res;
}


/***

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。
示例 1:

输入: [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

示例 2:
输入: [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。


 */

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public int findMaxLength(int[] nums) {
        int len = nums.length;

        Map<Integer, Integer> map = new HashMap<>(len);
        // 下标 0 之前的位置是 -1
        map.put(0, -1);

        int res = 0;
        int preSum = 0;

        // 把数组中的 0 都看成 -1
        for (int i = 0; i < len; i++) {
            // 把 0 视为 -1，pre 是先加了，所以后面计算的时候是 i - map.get(preSum)，注意下标 + 1 和不加 1 的差别
            if (nums[i] == 1) {
                preSum += 1;
            } else {
                preSum += -1;
            }

            if (map.containsKey(preSum)) {
                res = Math.max(res, i - map.get(preSum));
            } else {
                // 只记录这个数字第 1 次出现的下标
                map.put(preSum, i);
            }
        }
        return res;
    }
}


/**
https://leetcode.com/problems/word-pattern/
Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

 

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
<双射>

非常简洁，但是巧妙
1.put会返回前面的单词的映射的值

map.put(pattern.charAt(i), i) != map.put(words[i], i)


 */
public boolean wordPattern(String pattern, String str) {
        String[] words = str.split(" ");
        //字符和单词是互相映射，数量必须相等
        if (words.length != pattern.length()) {
            return false;
        }
        Map<Object, Integer> map = new HashMap<>();
        for (Integer i = 0; i < words.length; i++) {
            /*
                如果key不存在，插入成功，返回null；如果key存在，返回之前对应的value。

                以pattern = "abba", str = "dog cat cat dog"为例，
                第1次：map.put('a',0)返回null，map.put("dog",0)返回null，两者相等；
                第2次：map.put('b',1)返回null，map.put("cat",1)返回null，两者相等；
                第3次：map.put('b',2)返回1，map.put("cat",2)返回1，两者相等；
                第4次：map.put('a',3)返回0，map.put("dog",3)返回0，两者相等，
                结果为 true。

                以pattern = "abba", str = "dog cat cat fish"为例，
                第1次：map.put('a',0)返回null，map.put("dog",0)返回null，两者相等；
                第2次：map.put('b',1)返回null，map.put("cat",1)返回null，两者相等；
                第3次：map.put('b',2)返回1，map.put("cat",2)返回1，两者相等；
                第4次：map.put('a',3)返回0，map.put("fish",3)返回null，两者不相等，
                结果为 false。
            */
            if (map.put(pattern.charAt(i), i) != map.put(words[i], i)) {
                return false;
            }
        }
        return true;
    }
}






int findKthLargest(int[] nums, int k) {
    // 小顶堆，堆顶是最小元素
    PriorityQueue<Integer> 
        pq = new PriorityQueue<>();

    for (int i = 0; i < k; ++i) {
        queue.offer(arr[i]);
    }

    for (int i = k; i < arr.length; ++i) {
        if (queue.peek() < arr[i]) {
            queue.poll();
            queue.offer(arr[i]);
        }
    }    
    // 堆顶是最小的那个，即第 k 个最大元素
    return pq.peek();
}

/**
1.与二分查找很像
2.第k大，就是在升序数组里找第(len-k)的元素
3.partition返回值的含义，是数组中第K大值的index
 */
int findKthLargest(int[] nums, int k) {
    int lo = 0, hi = nums.length - 1;
    // 索引转化
    k = nums.length - k;
    while (lo <= hi) {
        // 在 nums[lo..hi] 中选一个分界点
        int p = partition(nums, lo, hi);

        if (p < k) {
            // 第 k 大的元素在 nums[p+1..hi] 中
            lo = p + 1;
        } else if (p > k) {
            // 第 k 大的元素在 nums[lo..p-1] 中
            hi = p - 1;
        } else {
            // 找到第 k 大元素
            return nums[p];
        }
    }
    return -1;
}

/**
我们用一个大根堆实时维护数组的前 k 小值。
首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。
最后将大根堆里的数存入数组返回即可
 */

/** 大根堆实时维护最小的K个数， 不断判断第k+1个数是不是能加入结果集 */
class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                //大根堆 默认小跟堆，左边减去右边
                return num2 - num1;
            }
        });
        for (int i = 0; i < k; ++i) {
            queue.offer(arr[i]);
        }

        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = queue.poll();
        }
        return vec;
    }
}
